ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ» Інженерно-технічний факультет Кафедра копм’ютерних систем та мереж Розрахунково-графічна робота з дисципліни «Теоретичні основи цифрової обробки сигналів» на тему: «Розрахунок параметрів виконання алгоритму ШПФ»  Завдання Варіант № 11 Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними: Кількість точок 1024  Основа ШПФ 4  Прорідження часове  Частота роботи процесора  1,8 МГц  Розрядність вхідних даних 20  Тип вхідного інтерфейсу CAN  Тип вихідного інтерфейсу USB   Анотація В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для 20-розрядних вхідних даних з часовим прорідженням: детально описано механізми обчислення швидкого перетворення Фур’є за заданною основою, обчислено часові ресурси для виконання обчислення, створена функціональна схема системи, написана програма, що реалізує вказаний алгоритм ШПФ.  Зміст Варіант № 11 2 Вступ 5 1 Опис швидкого перетворення Фур’є з прорідженням в часі 6 2 Розробка блок-схеми та метелика заданої функції, порядок слідування відліків 9 3 Розрахунковий розділ 12 4 Розробка функціональної схеми 14 5 Розробка програми виконання алгоритму ШПФ 16 Висновки 20 Література 21 Вступ Алгоритм швидкого перетворення Фур'є – є оптимізованим за швидкодією способом обчислення дискретного перетворення Фур'є (ДПФ), що має складність O(Nlog2N) на відміну від складності ДПФ порядку O(N2). Розробка процесора ШПФ на ПЛІС забезпечує однокристальну реалізацію процесора з високою продуктивністю і можливістю реконфігурації структури При цифровій обробці сигналів різної природи перетворення Фур’є звичайно розглядається як трансформація сигналу з часової ділянки в частотну, і навпаки, якщо відома частотна характеристика сигналу, то зворотне перетворення Фур’є дозволяє визначити відповідний сигнал у часовій області. Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. 1 Опис швидкого перетворення Фур’є з прорідженням в часі Дискретний матеріальний сигнал у вигляді кінцевої часової послідовності x(nТ) запишемо як x(nТ), де
- число відліків, N – число відліків, T – період дискретизації. N - точкове дискретне перетворення Фур’є (ДПФ) задається формулою:
де X(k) – частотний k-ий відлік чи k-а спектральна складова сигналу (визначає вихідну частотну послідовність, спектр сигналу),
комплексна експонента, W- ядро перетворення. При зміні значення n*k на величину кратну N ядро
не змінюється (у силу періодичності синуса і косинуса). Тобто ядро по верхньому індексу є періодичною функцією з періодом N. Тому замість добутку n*k можна вставити залишок від ділення його на N , тобто (n*k) mod N. Cпектральна функція X(k) також має період N по аргументу k. Число множень дійсних відліків сигналу на комплексне ядро в (1) дорівнює N2, а число додавань комплексних чисел – (N -1)N. Кількість цих операцій різко зростає із збільшенням N і приводить до занадто великого часу перетворення. ДПФ стало широко застосовуватися після винаходу швидких алгоритмів, в основі яких лежить принцип зведення багатоточкового перетворення до малоточкового. Один з них (що став уже класичним) називається ШПФ із проріджу-ванням за часом. Цей алгоритм отриманий за умови, якщо N є ступенем числа 2, тобто
, де ν - ціле число, ν≥0. Основні формули перетворення, до яких ми прийдемо, виходять при розбивці суми в (1) на дві суми, що містять відліки з парними і непарними номерами
Власне кажучи ця операція являє собою зміну порядку сумування (перегрупу-ва...